# coding: utf-8

from graph import Subgraph, vertex_t, vertex_map
from .RevEdges import RevEdges
from .CycleRemoval import CycleRemoval


class State:
    done = 0
    in_progress = 1
    unvisited = 2


"""
 * Algorithm for removing cycles in a graph using a depth first search.
"""


class DfsCycleRemoval(CycleRemoval):

    # def __init__(self, g: Subgraph):
    #     g = g
    #     self.marks = vertex_map(g, 'marks', State.unvisited)

    def run(self, g: Subgraph) -> RevEdges:
        # TODO
        # reversed_edges: RevEdges
        self.marks = vertex_map(g, "marks", State.unvisited)
        reversed_edges = RevEdges(g)
        for u in g.get_all_nodes():
            if self.marks[u] == State.unvisited:
                # TODO
                self.dfs(g, self.marks, 100000, u, reversed_edges)
        # print(self.marks)
        for u in g.get_all_nodes():
            if reversed_edges.reversed.data.contains(u):
                for v in reversed_edges.reversed.data[u]:
                    g.remove_edge(v, u)
                    g.add_edge(u, v)

            if reversed_edges.collapsed.data.contains(u):
                for v in reversed_edges.collapsed.data[u]:
                    g.remove_edge(v, u)

        for u in reversed_edges.loops:

            g.remove_edge(u, u)

        return reversed_edges

    def dfs(
        self,
        g: Subgraph,
        marks: vertex_map,
        parent: vertex_t,
        u: vertex_t,
        reversed_edges: RevEdges,
    ):
        # print('dfs:', u)
        marks[u] = State.in_progress
        # print('begain_dfs:', u, marks[u])

        for v in g.out_neighbours(u):
            if u == v:  # a loop
                reversed_edges.loops.append(u)
                print("loop", u)
            elif marks[v] == State.in_progress:  # there is a cycle
                if g.has_edge(v, u):  # two-cycle
                    reversed_edges.collapsed.insert(v, u)
                    print("two-cycle:", v, u)
                else:  # regular cycle
                    reversed_edges.reversed.insert(v, u)
                    print("regular cycle:", v, u)
            elif marks[v] == State.unvisited:
                self.dfs(g, self.marks, u, v, reversed_edges)

        marks[u] = State.done
        # print('end_dfs:', u, marks[u])
